package com.algs1_3;

import edu.princeton.cs.algs4.StdOut;

import java.util.Stack;

/**
 * Dijkstra的双栈算术表达式求值算法
 */
public class Evaluate {
    public static void main(String[] args) {
        // 运算符栈
        Stack<String> ops = new Stack<>();
        // 操作数栈
        Stack<Double> vals = new Stack<>();
        String str = "(1+((2+3)*(4*5)))";
        char ss[] = str.toCharArray();
        for(char c:ss){
            // 读取字符 如果是运算符则压入到运算符栈 ops
            String s = String.valueOf(c);
            // 左括号忽略
            if(s.equals("(")){
            }else if(s.equals("+")){
                ops.push(s);
            }else if(s.equals("-")){
                ops.push(s);
            }else if(s.equals("*")){
                ops.push(s);
            }else if(s.equals("/")){
                ops.push(s);
            }else if(s.equals(")")){
                // 右括号 弹出运算符合操作数 计算结果并压入到操作数栈
                String op = ops.pop();
                double v = vals.pop();
                if(op.equals("+")){
                    // 弹出2个
                    v = vals.pop() + v;
                }else if(op.equals("-")){
                    v = vals.pop() - v;
                }else if(op.equals("*")){
                    v = vals.pop() * v;
                }else if(op.equals("/")){
                    v = vals.pop() / v;
                }
                vals.push(v);
            }else{
                // 数值
                vals.push(Double.parseDouble(s));
            }
        }
        StdOut.println(vals.pop());
    }
}
